home *** CD-ROM | disk | FTP | other *** search
/ Visual Cafe 3 / Visual Cafe 3.ISO / Vcafe / Main.bin / Hashtable.java < prev    next >
Text File  |  1998-09-22  |  17KB  |  545 lines
  1. /*
  2.  * @(#)Hashtable.java    1.42 98/07/01
  3.  *
  4.  * Copyright 1995-1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  * 
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. import java.io.*;
  18.  
  19. /**
  20.  * Hashtable collision list.
  21.  */
  22. class HashtableEntry {
  23.     int hash;
  24.     Object key;
  25.     Object value;
  26.     HashtableEntry next;
  27.  
  28.     protected Object clone() {
  29.     HashtableEntry entry = new HashtableEntry();
  30.     entry.hash = hash;
  31.     entry.key = key;
  32.     entry.value = value;
  33.     entry.next = (next != null) ? (HashtableEntry)next.clone() : null;
  34.     return entry;
  35.     }
  36. }
  37.  
  38. /**
  39.  * This class implements a hashtable, which maps keys to values. Any 
  40.  * non-<code>null</code> object can be used as a key or as a value. 
  41.  * <p>
  42.  * To successfully store and retrieve objects from a hashtable, the 
  43.  * objects used as keys must implement the <code>hashCode</code> 
  44.  * method and the <code>equals</code> method. 
  45.  * <p>
  46.  * An instance of <code>Hashtable</code> has two parameters that 
  47.  * affect its efficiency: its <i>capacity</i> and its <i>load 
  48.  * factor</i>. The load factor should be between 0.0 and 1.0. When 
  49.  * the number of entries in the hashtable exceeds the product of the 
  50.  * load factor and the current capacity, the capacity is increased by 
  51.  * calling the <code>rehash</code> method. Larger load factors use 
  52.  * memory more efficiently, at the expense of larger expected time 
  53.  * per lookup. 
  54.  * <p>
  55.  * If many entries are to be made into a <code>Hashtable</code>, 
  56.  * creating it with a sufficiently large capacity may allow the 
  57.  * entries to be inserted more efficiently than letting it perform 
  58.  * automatic rehashing as needed to grow the table. 
  59.  * <p>
  60.  * This example creates a hashtable of numbers. It uses the names of 
  61.  * the numbers as keys: 
  62.  * <p><blockquote><pre>
  63.  *     Hashtable numbers = new Hashtable();
  64.  *     numbers.put("one", new Integer(1));
  65.  *     numbers.put("two", new Integer(2));
  66.  *     numbers.put("three", new Integer(3));
  67.  * </pre></blockquote>
  68.  * <p>
  69.  * To retrieve a number, use the following code: 
  70.  * <p><blockquote><pre>
  71.  *     Integer n = (Integer)numbers.get("two");
  72.  *     if (n != null) {
  73.  *         System.out.println("two = " + n);
  74.  *     }
  75.  * </pre></blockquote>
  76.  *
  77.  * @author  Arthur van Hoff
  78.  * @version 1.42, 07/01/98
  79.  * @see     java.lang.Object#equals(java.lang.Object)
  80.  * @see     java.lang.Object#hashCode()
  81.  * @see     java.util.Hashtable#rehash()
  82.  * @since   JDK1.0
  83.  */
  84. public
  85. class Hashtable extends Dictionary implements Cloneable, java.io.Serializable {
  86.     /**
  87.      * The hash table data.
  88.      */
  89.     private transient HashtableEntry table[];
  90.  
  91.     /**
  92.      * The total number of entries in the hash table.
  93.      */
  94.     private transient int count;
  95.  
  96.     /**
  97.      * Rehashes the table when count exceeds this threshold.
  98.      */
  99.     private int threshold;
  100.  
  101.     /**
  102.      * The load factor for the hashtable.
  103.      */
  104.     private float loadFactor;
  105.  
  106.     /** use serialVersionUID from JDK 1.0.2 for interoperability */
  107.     private static final long serialVersionUID = 1421746759512286392L;
  108.  
  109.     /**
  110.      * Constructs a new, empty hashtable with the specified initial 
  111.      * capacity and the specified load factor. 
  112.      *
  113.      * @param      initialCapacity   the initial capacity of the hashtable.
  114.      * @param      loadFactor        a number between 0.0 and 1.0.
  115.      * @exception  IllegalArgumentException  if the initial capacity is less
  116.      *               than or equal to zero, or if the load factor is less than
  117.      *               or equal to zero.
  118.      * @since      JDK1.0
  119.      */
  120.     public Hashtable(int initialCapacity, float loadFactor) {
  121.     if ((initialCapacity <= 0) || (loadFactor <= 0.0)) {
  122.         throw new IllegalArgumentException();
  123.     }
  124.     this.loadFactor = loadFactor;
  125.     table = new HashtableEntry[initialCapacity];
  126.     threshold = (int)(initialCapacity * loadFactor);
  127.     }
  128.  
  129.     /**
  130.      * Constructs a new, empty hashtable with the specified initial capacity
  131.      * and default load factor.
  132.      *
  133.      * @param   initialCapacity   the initial capacity of the hashtable.
  134.      * @since   JDK1.0
  135.      */
  136.     public Hashtable(int initialCapacity) {
  137.     this(initialCapacity, 0.75f);
  138.     }
  139.  
  140.     /**
  141.      * Constructs a new, empty hashtable with a default capacity and load
  142.      * factor. 
  143.      *
  144.      * @since   JDK1.0
  145.      */
  146.     public Hashtable() {
  147.     this(101, 0.75f);
  148.     }
  149.  
  150.     /**
  151.      * Returns the number of keys in this hashtable.
  152.      *
  153.      * @return  the number of keys in this hashtable.
  154.      * @since   JDK1.0
  155.      */
  156.     public int size() {
  157.     return count;
  158.     }
  159.  
  160.     /**
  161.      * Tests if this hashtable maps no keys to values.
  162.      *
  163.      * @return  <code>true</code> if this hashtable maps no keys to values;
  164.      *          <code>false</code> otherwise.
  165.      * @since   JDK1.0
  166.      */
  167.     public boolean isEmpty() {
  168.     return count == 0;
  169.     }
  170.  
  171.     /**
  172.      * Returns an enumeration of the keys in this hashtable.
  173.      *
  174.      * @return  an enumeration of the keys in this hashtable.
  175.      * @see     java.util.Enumeration
  176.      * @see     java.util.Hashtable#elements()
  177.      * @since   JDK1.0
  178.      */
  179.     public synchronized Enumeration keys() {
  180.     return new HashtableEnumerator(table, true);
  181.     }
  182.  
  183.     /**
  184.      * Returns an enumeration of the values in this hashtable.
  185.      * Use the Enumeration methods on the returned object to fetch the elements
  186.      * sequentially.
  187.      *
  188.      * @return  an enumeration of the values in this hashtable.
  189.      * @see     java.util.Enumeration
  190.      * @see     java.util.Hashtable#keys()
  191.      * @since   JDK1.0
  192.      */
  193.     public synchronized Enumeration elements() {
  194.     return new HashtableEnumerator(table, false);
  195.     }
  196.  
  197.     /**
  198.      * Tests if some key maps into the specified value in this hashtable.
  199.      * This operation is more expensive than the <code>containsKey</code>
  200.      * method.
  201.      *
  202.      * @param      value   a value to search for.
  203.      * @return     <code>true</code> if some key maps to the
  204.      *             <code>value</code> argument in this hashtable;
  205.      *             <code>false</code> otherwise.
  206.      * @exception  NullPointerException  if the value is <code>null</code>.
  207.      * @see        java.util.Hashtable#containsKey(java.lang.Object)
  208.      * @since      JDK1.0
  209.      */
  210.     public synchronized boolean contains(Object value) {
  211.     if (value == null) {
  212.         throw new NullPointerException();
  213.     }
  214.  
  215.     HashtableEntry tab[] = table;
  216.     for (int i = tab.length ; i-- > 0 ;) {
  217.         for (HashtableEntry e = tab[i] ; e != null ; e = e.next) {
  218.         if (e.value.equals(value)) {
  219.             return true;
  220.         }
  221.         }
  222.     }
  223.     return false;
  224.     }
  225.  
  226.     /**
  227.      * Tests if the specified object is a key in this hashtable.
  228.      * 
  229.      * @param   key   possible key.
  230.      * @return  <code>true</code> if the specified object is a key in this
  231.      *          hashtable; <code>false</code> otherwise.
  232.      * @see     java.util.Hashtable#contains(java.lang.Object)
  233.      * @since   JDK1.0
  234.      */
  235.     public synchronized boolean containsKey(Object key) {
  236.     HashtableEntry tab[] = table;
  237.     int hash = key.hashCode();
  238.     int index = (hash & 0x7FFFFFFF) % tab.length;
  239.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  240.         if ((e.hash == hash) && e.key.equals(key)) {
  241.         return true;
  242.         }
  243.     }
  244.     return false;
  245.     }
  246.  
  247.     /**
  248.      * Returns the value to which the specified key is mapped in this hashtable.
  249.      *
  250.      * @param   key   a key in the hashtable.
  251.      * @return  the value to which the key is mapped in this hashtable;
  252.      *          <code>null</code> if the key is not mapped to any value in
  253.      *          this hashtable.
  254.      * @see     java.util.Hashtable#put(java.lang.Object, java.lang.Object)
  255.      * @since   JDK1.0
  256.      */
  257.     public synchronized Object get(Object key) {
  258.     HashtableEntry tab[] = table;
  259.     int hash = key.hashCode();
  260.     int index = (hash & 0x7FFFFFFF) % tab.length;
  261.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  262.         if ((e.hash == hash) && e.key.equals(key)) {
  263.         return e.value;
  264.         }
  265.     }
  266.     return null;
  267.     }
  268.  
  269.     /**
  270.      * Rehashes the contents of the hashtable into a hashtable with a 
  271.      * larger capacity. This method is called automatically when the 
  272.      * number of keys in the hashtable exceeds this hashtable's capacity 
  273.      * and load factor. 
  274.      *
  275.      * @since   JDK1.0
  276.      */
  277.     protected void rehash() {
  278.     int oldCapacity = table.length;
  279.     HashtableEntry oldTable[] = table;
  280.  
  281.     int newCapacity = oldCapacity * 2 + 1;
  282.     HashtableEntry newTable[] = new HashtableEntry[newCapacity];
  283.  
  284.     threshold = (int)(newCapacity * loadFactor);
  285.     table = newTable;
  286.  
  287.     //System.out.println("rehash old=" + oldCapacity + ", new=" + newCapacity + ", thresh=" + threshold + ", count=" + count);
  288.  
  289.     for (int i = oldCapacity ; i-- > 0 ;) {
  290.         for (HashtableEntry old = oldTable[i] ; old != null ; ) {
  291.         HashtableEntry e = old;
  292.         old = old.next;
  293.  
  294.         int index = (e.hash & 0x7FFFFFFF) % newCapacity;
  295.         e.next = newTable[index];
  296.         newTable[index] = e;
  297.         }
  298.     }
  299.     }
  300.  
  301.     /**
  302.      * Maps the specified <code>key</code> to the specified 
  303.      * <code>value</code> in this hashtable. Neither the key nor the 
  304.      * value can be <code>null</code>. 
  305.      * <p>
  306.      * The value can be retrieved by calling the <code>get</code> method 
  307.      * with a key that is equal to the original key. 
  308.      *
  309.      * @param      key     the hashtable key.
  310.      * @param      value   the value.
  311.      * @return     the previous value of the specified key in this hashtable,
  312.      *             or <code>null</code> if it did not have one.
  313.      * @exception  NullPointerException  if the key or value is
  314.      *               <code>null</code>.
  315.      * @see     java.lang.Object#equals(java.lang.Object)
  316.      * @see     java.util.Hashtable#get(java.lang.Object)
  317.      * @since   JDK1.0
  318.      */
  319.     public synchronized Object put(Object key, Object value) {
  320.     // Make sure the value is not null
  321.     if (value == null) {
  322.         throw new NullPointerException();
  323.     }
  324.  
  325.     // Makes sure the key is not already in the hashtable.
  326.     HashtableEntry tab[] = table;
  327.     int hash = key.hashCode();
  328.     int index = (hash & 0x7FFFFFFF) % tab.length;
  329.     for (HashtableEntry e = tab[index] ; e != null ; e = e.next) {
  330.         if ((e.hash == hash) && e.key.equals(key)) {
  331.         Object old = e.value;
  332.         e.value = value;
  333.         return old;
  334.         }
  335.     }
  336.  
  337.     if (count >= threshold) {
  338.         // Rehash the table if the threshold is exceeded
  339.         rehash();
  340.         return put(key, value);
  341.     } 
  342.  
  343.     // Creates the new entry.
  344.     HashtableEntry e = new HashtableEntry();
  345.     e.hash = hash;
  346.     e.key = key;
  347.     e.value = value;
  348.     e.next = tab[index];
  349.     tab[index] = e;
  350.     count++;
  351.     return null;
  352.     }
  353.  
  354.     /**
  355.      * Removes the key (and its corresponding value) from this 
  356.      * hashtable. This method does nothing if the key is not in the hashtable.
  357.      *
  358.      * @param   key   the key that needs to be removed.
  359.      * @return  the value to which the key had been mapped in this hashtable,
  360.      *          or <code>null</code> if the key did not have a mapping.
  361.      * @since   JDK1.0
  362.      */
  363.     public synchronized Object remove(Object key) {
  364.     HashtableEntry tab[] = table;
  365.     int hash = key.hashCode();
  366.     int index = (hash & 0x7FFFFFFF) % tab.length;
  367.     for (HashtableEntry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
  368.         if ((e.hash == hash) && e.key.equals(key)) {
  369.         if (prev != null) {
  370.             prev.next = e.next;
  371.         } else {
  372.             tab[index] = e.next;
  373.         }
  374.         count--;
  375.         return e.value;
  376.         }
  377.     }
  378.     return null;
  379.     }
  380.  
  381.     /**
  382.      * Clears this hashtable so that it contains no keys. 
  383.      *
  384.      * @since   JDK1.0
  385.      */
  386.     public synchronized void clear() {
  387.     HashtableEntry tab[] = table;
  388.     for (int index = tab.length; --index >= 0; )
  389.         tab[index] = null;
  390.     count = 0;
  391.     }
  392.  
  393.     /**
  394.      * Creates a shallow copy of this hashtable. The keys and values 
  395.      * themselves are not cloned. 
  396.      * This is a relatively expensive operation.
  397.      *
  398.      * @return  a clone of the hashtable.
  399.      * @since   JDK1.0
  400.      */
  401.     public synchronized Object clone() {
  402.     try { 
  403.         Hashtable t = (Hashtable)super.clone();
  404.         t.table = new HashtableEntry[table.length];
  405.         for (int i = table.length ; i-- > 0 ; ) {
  406.         t.table[i] = (table[i] != null) 
  407.             ? (HashtableEntry)table[i].clone() : null;
  408.         }
  409.         return t;
  410.     } catch (CloneNotSupportedException e) { 
  411.         // this shouldn't happen, since we are Cloneable
  412.         throw new InternalError();
  413.     }
  414.     }
  415.  
  416.     /**
  417.      * Returns a rather long string representation of this hashtable.
  418.      *
  419.      * @return  a string representation of this hashtable.
  420.      * @since   JDK1.0
  421.      */
  422.     public synchronized String toString() {
  423.     int max = size() - 1;
  424.     StringBuffer buf = new StringBuffer();
  425.     Enumeration k = keys();
  426.     Enumeration e = elements();
  427.     buf.append("{");
  428.  
  429.     for (int i = 0; i <= max; i++) {
  430.         String s1 = k.nextElement().toString();
  431.         String s2 = e.nextElement().toString();
  432.         buf.append(s1 + "=" + s2);
  433.         if (i < max) {
  434.         buf.append(", ");
  435.         }
  436.     }
  437.     buf.append("}");
  438.     return buf.toString();
  439.     }
  440.  
  441.     /**
  442.      * WriteObject is called to save the state of the hashtable to a stream.
  443.      * Only the keys and values are serialized since the hash values may be
  444.      * different when the contents are restored.
  445.      * iterate over the contents and write out the keys and values.
  446.      */
  447.     private synchronized void writeObject(java.io.ObjectOutputStream s)
  448.         throws IOException
  449.     {
  450.     // Write out the length, threshold, loadfactor
  451.     s.defaultWriteObject();
  452.  
  453.     // Write out length, count of elements and then the key/value objects
  454.     s.writeInt(table.length);
  455.     s.writeInt(count);
  456.     for (int index = table.length-1; index >= 0; index--) {
  457.         HashtableEntry entry = table[index];
  458.  
  459.         while (entry != null) {
  460.         s.writeObject(entry.key);
  461.         s.writeObject(entry.value);
  462.         entry = entry.next;
  463.         }
  464.     }
  465.     }
  466.  
  467.     /**
  468.      * readObject is called to restore the state of the hashtable from
  469.      * a stream.  Only the keys and values are serialized since the
  470.      * hash values may be different when the contents are restored.
  471.      * Read count elements and insert into the hashtable. 
  472.      */
  473.     private synchronized void readObject(java.io.ObjectInputStream s)
  474.          throws IOException, ClassNotFoundException
  475.     {
  476.     // Read in the length, threshold, and loadfactor
  477.     s.defaultReadObject();
  478.  
  479.     // Read the original length of the array and number of elements
  480.     int origlength = s.readInt();
  481.     int elements = s.readInt();
  482.  
  483.     // Compute new size with a bit of room 5% to grow but
  484.     // No larger than the original size.  Make the length
  485.     // odd if it's large enough, this helps distribute the entries.
  486.     // Guard against the length ending up zero, that's not valid.
  487.     int length = (int)(elements * loadFactor) + (elements / 20) + 3;
  488.     if (length > elements && (length & 1) == 0)
  489.         length--;
  490.     if (origlength > 0 && length > origlength)
  491.         length = origlength;
  492.  
  493.     table = new HashtableEntry[length];
  494.     count = 0;
  495.  
  496.     // Read the number of elements and then all the key/value objects
  497.     for (; elements > 0; elements--) {
  498.         Object key = s.readObject();
  499.         Object value = s.readObject();
  500.         put(key, value);
  501.     }
  502.     }
  503. }
  504.  
  505. /**
  506.  * A hashtable enumerator class.  This class should remain opaque 
  507.  * to the client. It will use the Enumeration interface. 
  508.  */
  509. class HashtableEnumerator implements Enumeration {
  510.     boolean keys;
  511.     int index;
  512.     HashtableEntry table[];
  513.     HashtableEntry entry;
  514.  
  515.     HashtableEnumerator(HashtableEntry table[], boolean keys) {
  516.     this.table = table;
  517.     this.keys = keys;
  518.     this.index = table.length;
  519.     }
  520.     
  521.     public boolean hasMoreElements() {
  522.     if (entry != null) {
  523.         return true;
  524.     }
  525.     while (index-- > 0) {
  526.         if ((entry = table[index]) != null) {
  527.         return true;
  528.         }
  529.     }
  530.     return false;
  531.     }
  532.  
  533.     public Object nextElement() {
  534.     if (entry == null) {
  535.         while ((index-- > 0) && ((entry = table[index]) == null));
  536.     }
  537.     if (entry != null) {
  538.         HashtableEntry e = entry;
  539.         entry = e.next;
  540.         return keys ? e.key : e.value;
  541.     }
  542.     throw new NoSuchElementException("HashtableEnumerator");
  543.     }
  544. }
  545.